package com.zxy.javaarithmetic.chapter_2_LinkList;

/*
 *  @项目名：  study
 *  @包名：    com.zxy.javaarithmetic.chapter_2_LinkList
 *  @文件名:   P_2_RemoveLastKNode
 *  @创建者:   zhangxy
 *  @创建时间:  2018/12/6 11:04
 *  @描述：    分别实现两个函数，在单链表和双链表中删除倒数第k个节点
 */
public class P_2_RemoveLastKNode {

	public static void main(String[] args) {
		int[] data1 = new int[]{2, 3, 5, 6, 7, 8};
		Node head1 = new Node(data1[0]);
		Node temp = head1;
		for (int i = 1; i < data1.length; i++) {
			temp.next = new Node(data1[i]);
			temp = temp.next;
		}

		printNode(head1);
		head1 = removeLastKNode(head1, 2);
		printNode(head1);
		head1 = removeLastKNode(head1, 8);
		printNode(head1);
		head1 = removeLastKNode(head1, 5);
		printNode(head1);
	}

	private static void printNode(Node head) {
		Node cur = head;
		while (cur != null) {
			System.out.print(cur.value + "  ");
			cur = cur.next;
		}
		System.out.println("");
	}

	/**
	 * 删除单链表的倒数第k个节点
	 * @param head
	 * @param k
	 * @return
	 */
	private static Node removeLastKNode(Node head, int k) {
		if (head == null || head.next == null) {
			return head;
		}

		Node cur = head;
		while (cur != null) {
			k--;
			cur = cur.next;
		}

		if (k == 0) {
			head = head.next;
		} else if (k < 0) {
			cur = head;
			while (++k < 0) {
				cur = cur.next;
			}
			cur.next = cur.next.next;
		}
		return head;
	}

	/**
	 * 删除双向链表倒数第k个节点
	 * @param head
	 * @param k
	 * @return
	 */
	private static DoubleNode removeLastKDoubleNode(DoubleNode head, int k) {
		if (head == null || head.next == null) {
			return head;
		}

		DoubleNode cur = head;
		while (cur != null) {
			k--;
			cur = cur.next;
		}

		if (k == 0) {
			head = head.next;
			head.last = null;
		} else if (k < 0) {
			cur = head;
			while (++k < 0) {
				cur = cur.next;
			}
			DoubleNode curNext = cur.next.next;
			cur.next = curNext;
			if(curNext != null){
				curNext.last = cur;
			}
		}
		return head;
	}

}
